package study.datastructure.backtrack;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2025-02-16 12:18
 * <p>
 * 2025/2/16,
 * <p>
 * 2025/2/16,
 */

/**
 2025/2/16,
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 回溯
 */
public class s1 {

    /**
     * 全排列
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        backtrack(res, new boolean[nums.length], new ArrayList<>(), nums);
        return res;
    }

    private void backtrack(List<List<Integer>> res, boolean[] used
            , List<Integer> path, int[] nums) {


        // 路径 长度 等于数组长度 返回
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 遍历 所有元素排列
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {

                path.add(nums[i]);
                used[i] = true;

                backtrack(res, used, path, nums);

                // 回溯 撤销上一个选择
                path.remove(path.size() - 1);
                used[i] = false;
            }

        }

    }

    /**
     * 子集
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     *
     *
     * 回溯法：
     *
     * 从空集开始，逐步添加元素。
     * 每次递归处理一个元素，选择将其加入当前子集或不加入。
     * 通过维护起始索引，确保每个元素只处理一次，避免重复子集。
     * 解决代码
     * @param nums
     * @return
     */

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack1(res, 0, new ArrayList<>(), nums);
        return res;
    }

    private void backtrack1(List<List<Integer>> res, int start
            , List<Integer> path, int[] nums) {
        res.add(new ArrayList<>(path));
        // 遍历 所有元素排列
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack1(res, i + 1, path, nums);
            // 回溯 撤销上一个选择
            path.remove(path.size() - 1);
        }
    }

    /**
     * 电话号码的字母组合
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }

        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations
            , Map<Character, String> phoneMap, String digits
            , int index, StringBuffer combination) {

        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char charAt = digits.charAt(index);
            String s = phoneMap.get(charAt);
            for (int i = 0; i < s.length(); i++) {
                combination.append(s.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }

        }
    }
}
